package cn.good.yan.sf.t1;

import java.util.Arrays;

/**
 * 1. 合并有序数据
 *
 * @author shengren.yan
 * @create 2024-07-14
 */
public class Demo4 {

    // 参数： 原数组 、i 数组前的下标开始 、iEnd 数组前的下标结束 、j 数组后的下标开始 、jEnd 数组后的下标结束
    //      n 合并后的数组，k 合并后数组的下标
    public static void merge1(int[] arr,
                              int i,
                              int iEnd,
                              int j,
                              int jEnd,
                              int[] n,
                              int k) {
        if (i > iEnd) {
            System.arraycopy(arr, j, n, k, jEnd - j + 1);
            return;
        }
        if (j > jEnd) {
            System.arraycopy(arr, i, n, k, iEnd - i + 1);
            return;
        }

        if (i <= iEnd && j <= jEnd) {
            if (arr[i] < arr[j]) {
                n[k] = arr[i];
                merge1(arr, i + 1, iEnd, j, jEnd, n, k + 1);
            } else {
                n[k] = arr[j];
                merge1(arr, i, iEnd, j + 1, jEnd, n, k + 1);
            }
        }

    }

    public static void merge2(int[] arr, int i, int iEnd, int j, int jEnd, int[] n) {
        int k = 0;
        while (i <= iEnd && j <= jEnd) {
            if (arr[i] < arr[j]) {
                n[k] = arr[i];
                i++;
            } else {
                n[k] = arr[j];
                j++;
            }
            k++;
        }
        if (i > iEnd) {
            System.arraycopy(arr, j, n, k, jEnd - j + 1);
        }
        if (j > jEnd) {
            System.arraycopy(arr, i, n, k, iEnd - i + 1);
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 3, 5, 8};
        int[] b = {2, 4, 6, 9, 10, 12};
        int[] arr = new int[a.length + b.length];
        System.arraycopy(a, 0, arr, 0, a.length);
        System.arraycopy(b, 0, arr, a.length, b.length);
        int[] n = new int[arr.length];
        // 方式1
//        merge1(arr, 0, 3, 4, 9, n, 0);
        // 方式2
        merge2(arr, 0, 3, 4, 9, n);
        System.out.println(Arrays.toString(n));

    }
}
